
#define PAGE_PRESENT	0x1
#define PAGE_WRITE		0x2
#define PAGE_USER		0x4
#define HEAP_START 0xB0000000
#define HEAP_END 0xBFFFF000

typedef struct header_st
{
	struct header_st *prev, *next;
	unsigned int allocated : 1;
	unsigned int length : 31;
}header;

unsigned int heap_max = HEAP_START;
header *heap_first = 0;

unsigned int heap_m = 0;

void memcopy(unsigned char *dest, const unsigned char *src, unsigned int len)
{
	for(; len!=0; len--) *dest++ = *src++;
}

void memset(unsigned char *dest, unsigned char val, unsigned int len)
{
	for(; len!=0; len--) *dest++ = val;
}


void init_heap()
{
	
}

void alloc_chunk(unsigned int start, unsigned int length)
{
	while(start + length > heap_max)
	{
		map(heap_max, PAGE_PRESENT | PAGE_WRITE | PAGE_USER);
		heap_max += 0x1000;
	}
}

void free_chunk(header *chunk)
{
	chunk->prev->next = 0;
	
	if(chunk->prev == 0)
		heap_first = 0;
	
	while ((heap_max-0x1000) >= (unsigned int)chunk)
	{
		heap_max -= 0x1000;
		unmap(heap_max);
	}
}

void split_chunk(header *chunk, unsigned int length)
{
	if(chunk->length - length > sizeof(header))
	{
		header *newchunk = (header *)((unsigned int)chunk + length + sizeof(header));
		newchunk->prev = chunk;
		newchunk->next = chunk->next;
		newchunk->allocated = 0;
		newchunk->length = chunk->length - length;
		
		chunk->next = newchunk;
		chunk->length = length;
	}
}

void glue_chunk(header *chunk)
{
	if (chunk->next && chunk->next->allocated == 0)
	{
		chunk->length = chunk->length + chunk->next->length;
		if(chunk->next->next != 0)
		{
			chunk->next->next->prev = chunk;
		}
		chunk->next = chunk->next->next;
	}
	
	if(chunk->prev && chunk->prev->allocated == 0)
	{
		chunk->prev->length = chunk->prev->length + chunk->length;
		chunk->prev->next = chunk->next;
		if(chunk->next)
		{
			chunk->next->prev = chunk->prev;
		}
		chunk = chunk->prev;
	}
	
	if(chunk->next == 0)
	{
		free_chunk(chunk);
	}
}

void *malloc(unsigned int l)
{
	spin(&heap_m);
	l += sizeof(header);
	
	header *cur_header = heap_first, *prev_header = 0;
	while(cur_header)
	{
		if(cur_header->allocated == 0 && cur_header->length >= l)
		{
			split_chunk(cur_header, l);
			cur_header->allocated = 1;
			heap_m = 0;
			return (void *)((unsigned int)cur_header + sizeof(header));
		}
		prev_header = cur_header;
		cur_header = cur_header->next;
	}
	
	unsigned int chunk_start;
	if(prev_header)
	{
		chunk_start = (unsigned int)prev_header + prev_header->length;
	} else {
		chunk_start = HEAP_START;
		heap_first = (header *)chunk_start;
	}

	alloc_chunk(chunk_start, l);

	cur_header = (header *)chunk_start;
	cur_header->prev = prev_header;

	cur_header->next = 0;
	cur_header->allocated = 1;
	cur_header->length = l;

	if(prev_header)
		prev_header->next = cur_header;
	heap_m = 0;
	return (void *)((unsigned int)cur_header + sizeof(header));
}

void free(void *p)
{
	spin(&heap_m);
	header *head = (header *)((unsigned int)p - sizeof(header));
	head->allocated = 0;
	glue_chunk(head);
	heap_m = 0;
}

void *valloc(unsigned int l)
{
	l = 0x1000;
	unsigned int start = (unsigned int)malloc(l+ 0x1000 + sizeof(header));
	header *head = (header *)(start - sizeof(header));
	if(start%0x1000 > sizeof(header)){
		split_chunk(head,(0x1000-start%0x1000));
		head = head->next;
		head->allocated = 1;
		free((void *)((unsigned int)head->prev + sizeof(header)));
	} else {
		unsigned int old_length = head->length;
		header *next = head->next;
		header *prev = head->prev;
		
		prev->length = prev->length + (0x1000-start%0x1000);
		prev->next = (header *)((unsigned int)prev->next + (0x1000-start%0x1000));
		
		head = prev->next;
		head->next = next;
		head->prev = prev;
		head->allocated = 1;
		head->length = old_length - (0x1000-start%0x1000);
		
		if(head->next)
			head->next->prev = head;
	}
	split_chunk(head,0x1000);
	printf("\n next:%x",head->next);
	return (void *)((unsigned int)head + sizeof(header));
}
